#include<iostream>
#include<deque>
#include<cstring>
#include "Graph.h"

/**
	increase one edge
*/
void Graph::IncEdge(int from, int to){
	this->edge_num++;
	this->indegree[to]++;
	this->outdegree[from]++;
}

void Graph::DecEdge(int from, int to){
	this->edge_num--;
	this->indegree[to]--;
	this->outdegree[from]--;
}

Graph::Graph(int vertex_num){
	this->vertex_num = vertex_num;
	this->edge_num = 0;
	this->visited = new bool[this->vertex_num];
	this->indegree = new int[this->vertex_num];
	this->outdegree = new int[this->vertex_num];
	for(int i=0;i<this->vertex_num;i++){
		this->visited[i] = false;
		this->indegree[i] = 0;
		this->outdegree[i] = 0;
	}
}

Graph::Graph(const Graph& g):vertex_num(g.vertex_num),edge_num(g.edge_num){
	if(this!=&g){
		this->visited = new bool[this->vertex_num];
		this->indegree = new int[this->vertex_num];
		this->outdegree = new int[this->vertex_num];
		memcpy(this->visited,g.visited,sizeof(bool)*this->vertex_num);
		memcpy(this->indegree,g.indegree,sizeof(int)*this->vertex_num);
		memcpy(this->outdegree,g.outdegree,sizeof(int)*this->vertex_num);
	}
}

Graph& Graph::operator = (const Graph& g){
	if(this!=&g){
		this->vertex_num = g.vertex_num;
		this->edge_num = g.edge_num;
		this->visited = new bool[this->vertex_num];
		this->indegree = new int[this->vertex_num];
		this->outdegree = new int[this->vertex_num];
		memcpy(this->visited,g.visited,sizeof(bool)*this->vertex_num);
		memcpy(this->indegree,g.indegree,sizeof(int)*this->vertex_num);
		memcpy(this->outdegree,g.outdegree,sizeof(int)*this->vertex_num);

	}
	return *this;
}

Graph::~Graph(){
	delete[] this->visited;
	delete[] this->indegree;
	delete[] this->outdegree;
}

int Graph::GetVerticesNum(){
	return this->vertex_num;
}

int Graph::GetEdgeNum(){
	return this->edge_num;
}

void Graph::ClearVisitState(){
	for(int i=0;i<this->vertex_num;i++){
		this->visited[i] = false;
	}
}

void Graph::DeepFirstSearch(int vertex){
	if(vertex<this->vertex_num&&vertex>=0){
		this->Visit(vertex);
		this->visited[vertex] = true;
		for(Edge e = this->GetFirstEdge(vertex); this->IsEdge(e); e = this->GetNextEdge(e)){
			if(this->visited[e.to] == false){
				this->DeepFirstSearch(e.to);
			}
		}
	}else{
		std::cerr<<"Vertex id"<<vertex<<" is invalid!"<<std::endl;
	}
}

void Graph::BroadFirstSearch(int vertex){
	if(vertex<this->vertex_num&&vertex>=0){
		std::deque<int> queue;
		queue.push_back(vertex);
		while(!queue.empty()){
			vertex = queue.front(); queue.pop_front();
			if(this->visited[vertex]==false){
				this->Visit(vertex);
				this->visited[vertex] = true;
				for(Edge e = this->GetFirstEdge(vertex); this->IsEdge(e);e=this->GetNextEdge(e)){
					if(this->visited[e.to] == false){
						queue.push_back(e.to);
					}
				}
			}
		}
	}
}

void Graph::DoDeepFirstTraverse(){
	this->ClearVisitState();
	for(int i = 0; i<this->vertex_num;i++){
		if(this->visited[i]==false){
			this->DeepFirstSearch(i);
		}
	}
}

void Graph::DoBroadFirstTraverse(){
	this->ClearVisitState();
	for(int i = 0; i<this->vertex_num;i++){
		if(this->visited[i]==false){
			this->BroadFirstSearch(i);
		}
	}
}
